{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximize Palindrome Length From Subsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #由子序列构造的最长回文串的长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串 <code>word1</code> 和 <code>word2</code> ，请你按下述方法构造一个字符串：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从 <code>word1</code> 中选出某个 <strong>非空</strong> 子序列 <code>subsequence1</code> 。</li>\n",
    "\t<li>从 <code>word2</code> 中选出某个 <strong>非空</strong> 子序列 <code>subsequence2</code> 。</li>\n",
    "\t<li>连接两个子序列 <code>subsequence1 + subsequence2</code> ，得到字符串。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回可按上述方法构造的最长 <strong>回文串</strong> 的 <strong>长度</strong> 。如果无法构造回文串，返回 <code>0</code> 。</p>\n",
    "\n",
    "<p>字符串 <code>s</code> 的一个 <strong>子序列</strong> 是通过从 <code>s</code> 中删除一些（也可能不删除）字符而不更改其余字符的顺序生成的字符串。</p>\n",
    "\n",
    "<p><strong>回文串</strong> 是正着读和反着读结果一致的字符串。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>word1 = \"cacb\", word2 = \"cbba\"\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>从 word1 中选出 \"ab\" ，从 word2 中选出 \"cba\" ，得到回文串 \"abcba\" 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>word1 = \"ab\", word2 = \"ab\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>从 word1 中选出 \"ab\" ，从 word2 中选出 \"a\" ，得到回文串 \"aba\" 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>word1 = \"aa\", word2 = \"bb\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>无法按题面所述方法构造回文串，所以返回 0 。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= word1.length, word2.length &lt;= 1000</code></li>\n",
    "\t<li><code>word1</code> 和 <code>word2</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximize-palindrome-length-from-subsequences](https://leetcode.cn/problems/maximize-palindrome-length-from-subsequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximize-palindrome-length-from-subsequences](https://leetcode.cn/problems/maximize-palindrome-length-from-subsequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"cacb\"\\n\"cbba\"', '\"ab\"\\n\"ab\"', '\"aa\"\\n\"bb\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        n1 = len(word1)\n",
    "        ans = 0\n",
    "        f = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            pre = 1\n",
    "            for j in range(i, n):\n",
    "                tmp = f[j]\n",
    "                if i == j:\n",
    "                    f[j] = 1\n",
    "                elif s[i] == s[j]:\n",
    "                    f[j] = pre + 2\n",
    "                    if i < n1 <= j:\n",
    "                        ans = max(f[j], ans) \n",
    "                else:\n",
    "                    f[j] = max(f[j], f[j-1])\n",
    "                pre = tmp\n",
    "        return ans\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i > j :\n",
    "        #         return 0\n",
    "        #     if i == j:\n",
    "        #         return 1\n",
    "        #     if s[i] == s[j]:\n",
    "        #         res = dfs(i+1, j-1) + 2\n",
    "        #         if i < n1 <= j:\n",
    "        #             nonlocal ans\n",
    "        #             ans = max(res, ans)\n",
    "        #         return res\n",
    "        #     else:\n",
    "        #         return max(dfs(i+1, j), dfs(i, j-1))\n",
    "        # dfs(0, n-1)\n",
    "        # return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        ans, n = 0, len(s)\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            f[i] = 1\n",
    "            pre = 0\n",
    "            for j in range(i + 1, n):\n",
    "                tmp = f[j]\n",
    "                if s[i] == s[j]:\n",
    "                    f[j] = pre + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, f[j])\n",
    "                else:\n",
    "                    f[j] = max(f[j], f[j - 1])\n",
    "                pre = tmp\n",
    "        return ans    \n",
    "    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        word2=word2[::-1]\n",
    "        def longestPalindromeSubseq(s):\n",
    "            if len(s)<1:\n",
    "                return 0\n",
    "            n = len(s)\n",
    "            dp = [[0]*n for _ in range(n)]\n",
    "            for i in range(n):\n",
    "                dp[i][i] = 1\n",
    "            for i in range(n-1):\n",
    "                if s[i]==s[i+1]:\n",
    "                    dp[i][i+1]=2\n",
    "                else:\n",
    "                    dp[i][i+1]=1\n",
    "            \n",
    "            for l in range(2,n): # l表示考虑的子串的长度\n",
    "                for i in range(n-l):\n",
    "                    if s[i]==s[i+l]:\n",
    "                        dp[i][i+l]=dp[i+1][i+l-1]+2\n",
    "                    else:\n",
    "                        dp[i][i+l]=max(dp[i+1][i+l],dp[i][i+l-1])\n",
    "\n",
    "            return [dp[i][n-1] for i in range (0,n)]\n",
    "    \n",
    "        m=len(word1)\n",
    "        n=len(word2)\n",
    "        dp1=longestPalindromeSubseq(word1)\n",
    "        dp2=longestPalindromeSubseq(word2)\n",
    "        ans=0\n",
    "        dp=[[0 for _ in range (0,n)] for _ in range (0,m)]\n",
    "        for i in range (0,m):\n",
    "            for j in range (0,n):\n",
    "                if word1[i]==word2[j]:\n",
    "                    dp[i][j]=1\n",
    "        for i in range (0,m):\n",
    "            for j in range (0,n):\n",
    "                if i>0:\n",
    "                    dp[i][j]=max(dp[i][j],dp[i-1][j])\n",
    "                if j>0:\n",
    "                    dp[i][j]=max(dp[i][j],dp[i][j-1])\n",
    "                if i>0 and j>0 and word1[i]==word2[j]:\n",
    "                    dp[i][j]=max(dp[i][j],1+dp[i-1][j-1])\n",
    "        ans=0\n",
    "        for i in range (0,m):\n",
    "            for j in range (0,n):\n",
    "                if dp[i][j]>0:\n",
    "                    ans=max(ans,2*dp[i][j])\n",
    "                    if i<m-1:\n",
    "                        ans=max(ans,2*dp[i][j]+dp1[i+1])\n",
    "                    if j<n-1:\n",
    "                        ans=max(ans,2*dp[i][j]+dp2[j+1])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        # m = len(word1)\n",
    "        # self.ans = 0\n",
    "        # @cache\n",
    "        # def f(i,j):\n",
    "        #     if i> j:\n",
    "        #         return 0\n",
    "        #     if i==j:\n",
    "        #         return 1\n",
    "\n",
    "        #     if s[i] == s[j]:\n",
    "        #         cur = f(i+1,j-1) + 2\n",
    "        #         if i< m <= j:\n",
    "        #             self.ans = max(self.ans, cur)\n",
    "        #         return cur\n",
    "                \n",
    "        #     return max(f(i+1,j), f(i,j-1))\n",
    "        # f(0,len(s)-1)\n",
    "        # return self.ans\n",
    "        n,m = len(word1), len(word2)\n",
    "        a = '#' + word1\n",
    "        word2 = word2[::-1]\n",
    "        b = '#' + word2\n",
    "        f = [[0]*(m+1) for _ in range(n+1)]\n",
    "        fa = [[0] * (n+2) for _ in range(n+2)]\n",
    "        fb = [[0] * (m+2) for _ in range(m+2)]\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                f[i][j] = max(f[i-1][j],f[i][j-1])\n",
    "                if a[i] == b[j]:\n",
    "                    f[i][j] = max(f[i][j], f[i-1][j-1] + 1)\n",
    "        for i in range(n,0,-1):\n",
    "            for j in range(i,n+1):            \n",
    "                if i==j: fa[i][j]=1\n",
    "                else:\n",
    "                    fa[i][j] = max(fa[i+1][j],fa[i][j-1])\n",
    "                    if a[i]==a[j]:\n",
    "                        fa[i][j] = max(fa[i][j], fa[i+1][j-1] + 2)\n",
    "        for i in range(m,0,-1):\n",
    "            for j in range(i,m+1):            \n",
    "                if i==j: fb[i][j]=1\n",
    "                else:\n",
    "                    fb[i][j] = max(fb[i+1][j],fb[i][j-1])\n",
    "                    if b[i]==b[j]:\n",
    "                        fb[i][j] = max(fb[i][j], fb[i+1][j-1] + 2)\n",
    "        ans = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                if  f[i][j] >=1:\n",
    "                    ans = max(ans,f[i][j]*2 + max(fa[i+1][n],fb[j+1][m]))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        # m = len(word1)\n",
    "        # self.ans = 0\n",
    "        # @cache\n",
    "        # def f(i,j):\n",
    "        #     if i> j:\n",
    "        #         return 0\n",
    "        #     if i==j:\n",
    "        #         return 1\n",
    "\n",
    "        #     if s[i] == s[j]:\n",
    "        #         cur = f(i+1,j-1) + 2\n",
    "        #         if i< m <= j:\n",
    "        #             self.ans = max(self.ans, cur)\n",
    "        #         return cur\n",
    "                \n",
    "        #     return max(f(i+1,j), f(i,j-1))\n",
    "        # f(0,len(s)-1)\n",
    "        # return self.ans\n",
    "        n,m = len(word1), len(word2)\n",
    "        a = '#' + word1\n",
    "        word2 = word2[::-1]\n",
    "        b = '#' + word2\n",
    "        f = [[0]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                f[i][j] = max(f[i-1][j],f[i][j-1])\n",
    "                if a[i] == b[j]:\n",
    "                    f[i][j] = max(f[i][j], f[i-1][j-1] + 1)\n",
    "        def lp(word):\n",
    "            n = len(word)\n",
    "            a = '#' + word\n",
    "            fa = [[0] * (n+2) for _ in range(n+2)]\n",
    "            for i in range(n,0,-1):\n",
    "                for j in range(i,n+1):            \n",
    "                    if i==j: \n",
    "                        fa[i][j]=1\n",
    "                    else:\n",
    "                        fa[i][j] = max(fa[i+1][j],fa[i][j-1])\n",
    "                        if a[i]==a[j]:\n",
    "                            fa[i][j] = max(fa[i][j], fa[i+1][j-1] + 2)\n",
    "            return fa\n",
    "        fa = lp(word1)\n",
    "        fb = lp(word2)\n",
    "        ans = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                if  f[i][j] >=1:\n",
    "                    ans = max(ans,f[i][j]*2 + max(fa[i+1][n],fb[j+1][m]))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        word = word1 + word2\n",
    "        lw, cut = len(word), len(word1)\n",
    "        ret = 0\n",
    "        dp = [[0]*lw for _ in range(lw)]\n",
    "        for right in range(lw):\n",
    "            for left in range(right, -1, -1):\n",
    "                if left == right:\n",
    "                    dp[left][right] = 1\n",
    "                    continue\n",
    "                dp[left][right] = max(dp[left+1][right], dp[left][right-1])\n",
    "                if word[left] == word[right]:\n",
    "                    dp[left][right] = max(dp[left][right], 2+dp[left+1][right-1])\n",
    "                    if left < cut <= right:\n",
    "                        ret = max(ret, dp[left][right])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        # 模板：经典最长回文子序列矩阵DP\n",
    "        m, n = len(word1), len(word2)\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        dp = [[0] * (m + n) for _ in range(m + n)]\n",
    "        for i in range(m + n - 1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            if i + 1 < m + n:\n",
    "                dp[i][i + 1] = 2 if s[i] == s[i + 1] else 1\n",
    "            for j in range(i + 2, m + n):\n",
    "                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2)\n",
    "        for i in range(m):\n",
    "            for j in range(m+n-1, m-1, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    ans = max(ans, dp[i+1][j-1]+2)\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i+1][j-1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, f[i][j])\n",
    "                else:\n",
    "                    f[i][j] = max(f[i][j-1], f[i+1][j])\n",
    "        return ans\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i > j:\n",
    "        #         return 0\n",
    "        #     if i == j:\n",
    "        #         return 1\n",
    "        #     if s[i] == s[j]:\n",
    "        #         res = dfs(i+1, j-1) + 2\n",
    "        #         if i < len(word1) <= j:\n",
    "        #             nonlocal ans\n",
    "        #             ans = max(ans, res)\n",
    "        #         return res\n",
    "        #     return max(dfs(i+1, j), dfs(i, j-1))\n",
    "        # dfs(0, len(s)-1)\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        n,m = len(word1), len(word2)\n",
    "        sr = word1 + word2\n",
    "        ans = 0\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i >= j:\n",
    "        #         return 1 if i==j else 0\n",
    "        #     if sr[i] == sr[j]:\n",
    "        #         cur = dfs(i+1, j-1) + 2\n",
    "        #         if i < n and j >= n:\n",
    "        #             nonlocal ans\n",
    "        #             ans = max(ans, cur)\n",
    "        #         return cur\n",
    "        #     return max(dfs(i+1,j), dfs(i, j-1))\n",
    "        # dfs(0, m+n-1)\n",
    "        # return ans\n",
    "\n",
    "        dp = [ [0]  *len(sr) for _ in range(len(sr))]\n",
    "        for i in range(len(sr)-1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i+1, len(sr)):\n",
    "                if sr[i] == sr[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1] + 2\n",
    "                    #在最长回文子串上加一个判断，字符分别在两个word里，才更新最长\n",
    "                    if i < n and j >= n:\n",
    "                        ans = max(ans, dp[i][j])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])\n",
    "\n",
    "        # print(dp)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s=word1+word2\n",
    "        n=len(s)\n",
    "        f=[[0]*(n) for _ in range(n)]\n",
    "        ans=0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            f[i][i]=1\n",
    "            for j in range(i+1,n):\n",
    "                if s[i]==s[j]:\n",
    "                    f[i][j]=f[i+1][j-1]+2\n",
    "                    if i<len(word1)<=j:\n",
    "                        ans=max(ans,f[i][j])\n",
    "                else:\n",
    "                    f[i][j]=max(f[i+1][j],f[i][j-1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        ans, n = 0, len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        max = lambda x, y: x if x > y else y\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i + 1][j - 1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, f[i][j])\n",
    "                else: f[i][j] = max(f[i + 1][j], f[i][j - 1])\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    res = 0\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1 , -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j - 1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        self.res = max(self.res, dp[i][j])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])\n",
    "        return self.res\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i > j:\n",
    "        #         return 0\n",
    "        #     if i == j:\n",
    "        #         return 1\n",
    "        #     if s[i] == s[j]:\n",
    "        #         tmp = 2 + dfs(i + 1, j - 1)\n",
    "        #         if i < len(word1) <= j:\n",
    "        #             self.res = max(self.res, tmp)\n",
    "        #         return tmp\n",
    "        #     else:\n",
    "        #         return max(dfs(i + 1, j), dfs(i, j - 1))\n",
    "        # dfs(0, n - 1)\n",
    "        # return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        \n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        dp = [[0]*(n) for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i+1,n):\n",
    "                if s[i] == s[j]:\n",
    "                    # if i+1>j-1:\n",
    "                    #     print(i+1,j-1)\n",
    "                    dp[i][j] = dp[i+1][j-1]+2\n",
    "                    if i<len(word1)<=j:\n",
    "                        ans = max(ans, dp[i][j])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])\n",
    "        # print(dp)\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j - 1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, dp[i][j]) # dp[i][j] 一定包含 s[i] 和 s[j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        # cacb cbba \n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        n1 = len(word1)\n",
    "        ans = 0\n",
    "\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1] + 2\n",
    "                    if i < n1 <= j:\n",
    "                        ans = max(ans, dp[i][j])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])\n",
    "        return ans\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i > j:\n",
    "        #         return 0\n",
    "        #     if i == j:\n",
    "        #         return 1\n",
    "        #     if s[i] == s[j]:\n",
    "        #         res = dfs(i + 1, j - 1) + 2\n",
    "        #         if i < n1 <= j:\n",
    "        #             nonlocal ans\n",
    "        #             ans = max(ans, res)\n",
    "        #         return res\n",
    "        #     else:\n",
    "        #         return max(dfs(i+1, j), dfs(i, j-1))\n",
    "        \n",
    "        # dfs(0, n-1)\n",
    "        # return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        word=word1+word2\n",
    "        n=len(word)\n",
    "        # ans=0\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i>j:\n",
    "        #         return 0\n",
    "        #     if i==j:\n",
    "        #         return 1\n",
    "        #     if word[i]==word[j]:\n",
    "        #         res=dfs(i+1,j-1)+2\n",
    "        #         if i<len(word1)<=j:\n",
    "        #             nonlocal ans\n",
    "        #             ans=max(res,ans)\n",
    "        #         return ans\n",
    "        #     return max(dfs(i,j-1),dfs(i+1,j))\n",
    "        # dfs(0,n-1)\n",
    "        # return ans\n",
    "        dp=[[0]*n for _ in range(n)]\n",
    "        ans=0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dp[i][i]=1\n",
    "            for j in range(i+1,n):\n",
    "                res=0\n",
    "                if word[i]==word[j]:\n",
    "                    dp[i][j]=dp[i+1][j-1]+2\n",
    "                    if i<len(word1)<=j:\n",
    "                        ans=max(ans,dp[i][j])\n",
    "                else:\n",
    "                    dp[i][j]=max(dp[i+1][j],dp[i][j-1])\n",
    "\n",
    "                \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i+1][j-1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, f[i][j])\n",
    "                else:\n",
    "                    f[i][j] = max(f[i][j-1], f[i+1][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        # # 两个串拼接然后删除得到的回文串\n",
    "        word = word1 + word2\n",
    "        n = len(word)\n",
    "        dp = [[0]*(n) for i in range(n)]\n",
    "        # # 直接找正逆向的最长匹配字符串\n",
    "        # # 由于要求子序列非空\n",
    "        # for i in range(len(word1)):\n",
    "        #     for j in range(len(word2)):\n",
    "        #         if word[i] == word[n-1-j]:\n",
    "        #             dp[i+1][j+1] = dp[i][j] + 2\n",
    "                # 如果从两侧向中间，则需要补充当前是否两边都选到。\n",
    "                # 由于任何状态都可能从j=0直接传递过来，所以很难直接判断\n",
    "                # 如果i<len(word1) and j< len(word2):\n",
    "\n",
    "\n",
    "        #         else:\n",
    "        #             dp[i+1][j+1] = min(dp[i][j+1],dp[i+1][j])  \n",
    "        ans = 0\n",
    "        for i in range(n-1,-1,-1): #i向左移动\n",
    "            dp[i][i] = 1 # 先选自己\n",
    "            for j in range(i+1,n):  # i=n-1时无j可选，所以不会出界\n",
    "                if word[i] == word[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1] + 2\n",
    "                    # 只有这一步可以确保转移状态包含特定的i和j\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans,dp[i][j]) \n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j],dp[i][j-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        ans, n = 0, len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i + 1][j - 1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, f[i][j])  # f[i][j] 一定包含 s[i] 和 s[j]\n",
    "                else:\n",
    "                    f[i][j] = max(f[i + 1][j], f[i][j - 1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        ans, n = 0, len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i + 1][j - 1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, f[i][j])  # f[i][j] 一定包含 s[i] 和 s[j]\n",
    "                else:\n",
    "                    f[i][j] = max(f[i + 1][j], f[i][j - 1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\r\n",
    "        s = word1 + word2\r\n",
    "        ans, n = 0, len(s)\r\n",
    "        f = [[0] * n for _ in range(n)]\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            f[i][i] = 1\r\n",
    "            for j in range(i + 1, n):\r\n",
    "                if s[i] == s[j]:\r\n",
    "                    f[i][j] = f[i + 1][j - 1] + 2\r\n",
    "                    if i < len(word1) <= j:\r\n",
    "                        ans = max(ans, f[i][j])  # f[i][j] 一定包含 s[i] 和 s[j]\r\n",
    "                else:\r\n",
    "                    f[i][j] = max(f[i + 1][j], f[i][j - 1])\r\n",
    "        return ans\r\n",
    "        \r\n",
    "\r\n",
    "    def longestPalindrome2(self, word1: str, word2: str) -> int:\r\n",
    "        s = word1 + word2\r\n",
    "        ans = 0\r\n",
    "        @cache\r\n",
    "        def dfs(i: int, j: int) -> int:\r\n",
    "            if i > j: return 0\r\n",
    "            if i == j: return 1\r\n",
    "            if s[i] == s[j]:\r\n",
    "                res = dfs(i + 1, j - 1) + 2\r\n",
    "                if i < len(word1) <= j:\r\n",
    "                    nonlocal ans\r\n",
    "                    ans = max(ans, res)\r\n",
    "                return res\r\n",
    "            return max(dfs(i + 1, j), dfs(i, j - 1))\r\n",
    "        dfs(0, len(s) - 1)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i+1][j-1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, f[i][j])\n",
    "                else:\n",
    "                    f[i][j] =  max(f[i+1][j], f[i][j-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1+word2#求最长回文序列\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dp[i][i] = 1 #i == j的时候，结果为1\n",
    "            for j in range(i+1,n):\n",
    "                if s[i] == s[j]:\n",
    "                    #只有递归i < len(word1) <= j，才满足要求\n",
    "                    dp[i][j] = dp[i+1][j-1]+2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans,dp[i][j])  \n",
    "                else :\n",
    "                    dp[i][j] = max(dp[i+1][j],dp[i][j-1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1), len(word2)\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        dp = [[0] * (m + n) for _ in range(m + n)]\n",
    "        for i in range(m + n - 1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            if i + 1 < m + n:\n",
    "                dp[i][i + 1] = 2 if s[i] == s[i + 1] else 1\n",
    "            for j in range(i + 2, m + n):\n",
    "                dp[i][j] = ac_max(dp[i + 1][j], dp[i][j - 1])\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = ac_max(dp[i][j], dp[i + 1][j - 1] + 2)\n",
    "        for i in range(m):\n",
    "            for j in range(m+n-1, m-1, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    ans = ac_max(ans, dp[i+1][j-1]+2)\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        # 递推\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i + 1][j - 1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, f[i][j])\n",
    "                else:\n",
    "                    f[i][j] = max(f[i + 1][j], f[i][j - 1])\n",
    "        return ans\n",
    "\n",
    "        # 记忆化搜索\n",
    "        # s = word1 + word2\n",
    "        # n = len(s)\n",
    "        # ans = 0\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i > j:\n",
    "        #         return 0\n",
    "        #     elif i == j:\n",
    "        #         return 1\n",
    "            \n",
    "        #     if s[i] == s[j]:\n",
    "        #         res = dfs(i + 1, j - 1) + 2\n",
    "        #         if i < len(word1) <= j:\n",
    "        #             nonlocal ans\n",
    "        #             ans = max(ans, res)\n",
    "        #         return ans\n",
    "        #     return max(dfs(i + 1, j), dfs(i, j - 1))\n",
    "\n",
    "        # dfs(0, n - 1)\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1+word2\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i+1,n):\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1]+2\n",
    "                    if i<len(word1)<=j:\n",
    "                        ans = max(ans,dp[i][j])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j],dp[i][j-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        ans, n = 0, len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i + 1][j - 1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, f[i][j])\n",
    "                else:\n",
    "                    f[i][j] = max(f[i + 1][j], f[i][j - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        ans, n = 0, len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        # s[i:j]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j - 1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, dp[i][j])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i + 1][j - 1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, f[i][j])\n",
    "                else:\n",
    "                    f[i][j] = max(f[i + 1][j], f[i][j - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s, t, result = word1 + word2, (m := len(word1)) + (n := len(word2)), 0\n",
    "        f = [[0] * t for _ in range(t)]\n",
    "        for i in range(t):\n",
    "            f[i][i] = 1\n",
    "        for i in range(t - 1, -1, -1):\n",
    "            for j in range(i + 1, t):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i + 1][j - 1] + 2\n",
    "                    if i < m and j >= m:\n",
    "                        result = max(result, f[i][j])\n",
    "                else:\n",
    "                    f[i][j] = max(f[i + 1][j], f[i][j - 1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        ans, n = 0, len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i + 1][j - 1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, f[i][j])  # f[i][j] 一定包含 s[i] 和 s[j]\n",
    "                else:\n",
    "                    f[i][j] = max(f[i + 1][j], f[i][j - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        f = [[0] * n for i in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i + 1][j - 1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, f[i][j])\n",
    "                else:\n",
    "                    f[i][j] = max(f[i + 1][j], f[i][j - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, dp[i][j])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1), len(word2)\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        dp = [[0] * (m + n) for _ in range(m + n)]\n",
    "        for i in range(m + n - 1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            if i + 1 < m + n:\n",
    "                dp[i][i + 1] = 2 if s[i] == s[i + 1] else 1\n",
    "                if i == m-1 and s[i] == s[i + 1]:\n",
    "                    ans = ac_max(ans, 2)\n",
    "            for j in range(i + 2, m + n):\n",
    "                dp[i][j] = ac_max(dp[i + 1][j], dp[i][j - 1])\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = ac_max(dp[i][j], dp[i + 1][j - 1] + 2)\n",
    "                    if i < m and j >= m:\n",
    "                        ans = ac_max(ans, dp[i + 1][j - 1] + 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "\n",
    "        f =  [[0] * n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i+1][j-1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans  = max(ans, f[i][j])\n",
    "                else:\n",
    "                    f[i][j] = max(f[i+1][j],f[i][j-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "\n",
    "        m = len(word1)\n",
    "        ans = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i+1][j-1] + 2 \n",
    "                    if i < m and j >= m:\n",
    "                        ans = max(ans, f[i][j])\n",
    "                else:\n",
    "                    f[i][j] = max(f[i+1][j], f[i][j-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def max_(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def min_(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1), len(word2)\n",
    "        s = word1 + word2\n",
    "\n",
    "        dp = [[0]*(m+n) for _ in range(m+n)]\n",
    "        for i in range(m+n-1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            if i+1<m+n:\n",
    "                dp[i][i+1] = 2 if s[i] == s[i+1] else 1\n",
    "            for j in range(i+2, m+n):\n",
    "                dp[i][j] = max_(dp[i+1][j], dp[i][j-1])\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = max_(dp[i][j], dp[i+1][j-1]+2)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(m, m+n):\n",
    "                if s[i] == s[j]:\n",
    "                    ans = max_(ans, dp[i+1][j-1]+2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1), len(word2)\n",
    "        S = word1 + word2\n",
    "        N = len(S)\n",
    "        dp = [[0] * N for _ in range(N)]\n",
    "        res = 0\n",
    "        for span in range(1, N + 1):\n",
    "            for left in range(N - span + 1):\n",
    "                right = left + span - 1\n",
    "                if span == 1:\n",
    "                    dp[left][right] = 1\n",
    "                else:\n",
    "                    dp[left][right] = max(dp[left + 1][right], dp[left][right - 1])\n",
    "                    if S[left] == S[right]:\n",
    "                        dp[left][right] = dp[left + 1][right - 1] + 2\n",
    "                        if left < m <= right:\n",
    "                            res = max(res, dp[left][right])\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        word = word1 + word2\n",
    "        n = len(word)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        \n",
    "        # Initialize DP array for single-character palindromes\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "            \n",
    "        for length in range(2, n + 1):\n",
    "            for i in range(0, n - length + 1):\n",
    "                j = i + length - 1\n",
    "                if word[i] == word[j]:\n",
    "                    dp[i][j] = dp[i + 1][j - 1] + 2 if length > 2 else 2\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])\n",
    "        \n",
    "        max_length = 0\n",
    "        for i in range(len(word1)):\n",
    "            for j in range(len(word1), n):\n",
    "                if word[i] == word[j]:\n",
    "                    max_length = max(max_length, dp[i][j])\n",
    "        \n",
    "        return max_length\n",
    "\n",
    "# Test the code\n",
    "sol = Solution()\n",
    "print(sol.longestPalindrome(\"cacb\", \"cbba\"))  # Should output 5\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        # 模板：经典最长回文子序列矩阵DP\n",
    "        m, n = len(word1), len(word2)\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        dp = [[0] * (m + n) for _ in range(m + n)]\n",
    "        for i in range(m + n - 1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            if i + 1 < m + n:\n",
    "                dp[i][i + 1] = 2 if s[i] == s[i + 1] else 1\n",
    "            for j in range(i + 2, m + n):\n",
    "                a, b = dp[i + 1][j], dp[i][j - 1]\n",
    "                dp[i][j] = a if a > b else b\n",
    "                if s[i] == s[j]:\n",
    "                    a, b = dp[i][j], dp[i + 1][j - 1] + 2\n",
    "                    dp[i][j] = a if a > b else b\n",
    "        for i in range(m):\n",
    "            for j in range(m+n-1, m-1, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    a, b = ans, dp[i+1][j-1]+2\n",
    "                    ans = a if a > b else b\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        word = word1 + word2\n",
    "        n = len(word)\n",
    "        dp = [[0 for i in range(n)] for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if word[i] == word[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1] + 2\n",
    "                    if i < len(word1) <= j:\n",
    "                        ans = max(ans, dp[i][j])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s1, s2 = set(word1), set(word2)\n",
    "        if all(ch not in s2 for ch in s1):\n",
    "            return 0\n",
    "\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(l, r):\n",
    "            if l == r:\n",
    "                return 1\n",
    "            if l > r:\n",
    "                return 0\n",
    "            if s[l] == s[r]:\n",
    "                return 2 + dfs(l + 1, r - 1)\n",
    "            return max(dfs(l + 1, r), dfs(l, r - 1))\n",
    "\n",
    "        ans = 0\n",
    "        d1, d2 = {}, {}\n",
    "        for i, ch in enumerate(word2):\n",
    "            d2[ch] = i\n",
    "\n",
    "        for i, ch in enumerate(word1):\n",
    "            if ch in d2:\n",
    "                ans = max(ans, dfs(i, d2[ch] + len(word1)))\n",
    "\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        n = len(word1)\n",
    "        s = word1 + word2\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(l, r):\n",
    "            if l == r:\n",
    "                return 1\n",
    "            if l > r:\n",
    "                return 0\n",
    "            if s[l] == s[r]:\n",
    "                return 2 + dfs(l + 1, r - 1)\n",
    "            return max(dfs(l + 1, r), dfs(l, r - 1))\n",
    "\n",
    "        ans = 0\n",
    "        dic = {}\n",
    "        for i, ch in enumerate(word2):\n",
    "            dic[ch] = n + i\n",
    "        for i, ch in enumerate(word1):\n",
    "            if ch in dic:\n",
    "                ans = max(ans, dfs(i, dic[ch]))\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "最长回文串\n",
    "f[i][j]=f[i+1][j],f[i][j-1],f[i+1][j-1]+2\n",
    "'''\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s1=set(word1)\n",
    "        s2=set(word2)\n",
    "        if not s1&s2:\n",
    "            return 0\n",
    "        f=[[0]*len(word1) for _ in range(len(word1))]\n",
    "        for i in range(len(word1)-1,-1,-1):\n",
    "            f[i][i]=1\n",
    "            for j in range(i+1,len(word1)):\n",
    "                if word1[i]==word1[j]:\n",
    "                    f[i][j]=f[i+1][j-1]+2\n",
    "                else:\n",
    "                    f[i][j]=max(f[i+1][j],f[i][j-1])\n",
    "        g=[[0]*len(word2) for _ in range(len(word2))]\n",
    "        for i in range(len(word2)-1,-1,-1):\n",
    "            g[i][i]=1\n",
    "            for j in range(i+1,len(word2)):\n",
    "                if word2[i]==word2[j]:\n",
    "                    g[i][j]=g[i+1][j-1]+2\n",
    "                else:\n",
    "                    g[i][j]=max(g[i+1][j],g[i][j-1])\n",
    "        \n",
    "\n",
    "        @cache\n",
    "        def dfs(i:int,j:int,choose:bool)->int:\n",
    "            if i>=len(word1):\n",
    "                if not choose:return -inf\n",
    "                return g[0][j] if j>=0 else 0\n",
    "            if j<0:\n",
    "                if not choose:return -inf\n",
    "                return f[i][len(word1)-1] if i<len(word1) else 0\n",
    "            ans=-inf\n",
    "            if word1[i]==word2[j]:\n",
    "                ans=dfs(i+1,j-1,True)+2\n",
    "            ans=max(ans,dfs(i,j-1,choose),dfs(i+1,j,choose))\n",
    "            return ans\n",
    "        ans=dfs(0,len(word2)-1,False)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            nonlocal ans\n",
    "            if i == j: return 1\n",
    "            if i > j: return 0\n",
    "            if s[i] == s[j]:\n",
    "                print(i, j)\n",
    "                if i < len(word1) <= j:\n",
    "                    #print(i, j)\n",
    "                    ans = max(ans, dfs(i + 1, j - 1) + 2)\n",
    "                return dfs(i + 1, j - 1) + 2\n",
    "            return max(dfs(i, j - 1), dfs(i + 1, j))\n",
    "        dfs(0, n - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            nonlocal ans\n",
    "            if i == j: return 1\n",
    "            if i > j: return 0\n",
    "            if s[i] == s[j]:\n",
    "                #print(i, j)\n",
    "                if i < len(word1) <= j:\n",
    "                    #print(i, j)\n",
    "                    ans = max(ans, dfs(i + 1, j - 1) + 2)\n",
    "                return dfs(i + 1, j - 1) + 2\n",
    "            return max(dfs(i, j - 1), dfs(i + 1, j))\n",
    "        dfs(0, n - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        n1 = len(word1)\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j: return 0\n",
    "            if i == j: return 1\n",
    "            if s[i] == s[j]: return 2 + dfs(i + 1, j - 1)\n",
    "            return max(dfs(i + 1, j), dfs(i, j - 1))\n",
    "        res = 0\n",
    "        st = set()\n",
    "        for x in set(s):\n",
    "            i, j = s.index(x), s.rindex(x)\n",
    "            if i < n1 and j >= n1: res = max(res, dfs(i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i + 1, j - 1) + 2\n",
    "                if i < len(word1) <= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans, res)\n",
    "                return res\n",
    "            return max(dfs(i + 1, j), dfs(i, j - 1))\n",
    "\n",
    "        dfs(0, n - 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        # 递推\n",
    "        # s = word1 + word2\n",
    "        # ans = 0\n",
    "        # n = len(s)\n",
    "\n",
    "        # f = [[0] * n for _ in range(n)]\n",
    "        # for i in range(n - 1, -1, -1):\n",
    "        #     f[i][i] = 1\n",
    "        #     for j in range(i + 1, n):\n",
    "        #         if s[i] == s[j]:\n",
    "        #             f[i][j] = f[i + 1][j - 1] + 2\n",
    "        #             if i < len(word1) <= j:\n",
    "        #                 ans = max(ans, f[i][j])\n",
    "        #         else:\n",
    "        #             f[i][j] = max(f[i + 1][j], f[i][j - 1])\n",
    "        # return ans\n",
    "\n",
    "        # 记忆化搜索\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            elif i == j:\n",
    "                return 1\n",
    "            \n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i + 1, j - 1) + 2\n",
    "                if i < len(word1) <= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans, res)\n",
    "                return res\n",
    "            return max(dfs(i + 1, j), dfs(i, j - 1))\n",
    "\n",
    "        dfs(0, n - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    res = 0\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                tmp = 2 + dfs(i + 1, j - 1)\n",
    "                if i < len(word1) <= j:\n",
    "                    self.res = max(self.res, tmp)\n",
    "                return tmp\n",
    "            else:\n",
    "                return max(dfs(i + 1, j), dfs(i, j - 1))\n",
    "        dfs(0, n - 1)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        # s = word1 + word2\n",
    "        # ans, n = 0, len(s)\n",
    "        # f = [[0] * n for _ in range(n)]\n",
    "        # for i in range(n-1, -1, -1):\n",
    "        #     f[i][i] = 1\n",
    "        #     for j in range(i+1, n):\n",
    "        #         if s[i] == s[j]:\n",
    "        #             f[i][j] = f[i+1][j-1] + 2\n",
    "        #             if i < len(word1) <= j:\n",
    "        #                 ans = max(ans, f[i][j])\n",
    "        #         else:\n",
    "        #             f[i][j] = max(f[i+1][j], f[i][j-1])\n",
    "        # return ans\n",
    "        s = word1 + word2\n",
    "        ans, n = 0, len(s)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i+1, j-1) + 2\n",
    "                if i < len(word1) <= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans, res)\n",
    "                return res\n",
    "            return max(dfs(i+1, j), dfs(i, j-1))\n",
    "        dfs(0, n-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        # cacb cbba \n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        n1 = len(word1)\n",
    "        ans = 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i + 1, j - 1) + 2\n",
    "                if i < n1 <= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans, res)\n",
    "                return res\n",
    "            else:\n",
    "                return max(dfs(i+1, j), dfs(i, j-1))\n",
    "        \n",
    "        dfs(0, n-1)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i > j: return 0\n",
    "            if i == j: return 1\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i + 1, j - 1) + 2\n",
    "                if i < len(word1) <= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans, res)\n",
    "                return res\n",
    "            return max(dfs(i + 1, j), dfs(i, j - 1))\n",
    "        dfs(0, len(s) - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i>j:return 0\n",
    "            if i == j:return 1\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i+1,j-1)+2\n",
    "                if i < len(word1) <= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans, res)\n",
    "                return res\n",
    "            return max(dfs(i+1,j),dfs(i,j-1))\n",
    "        dfs(0,n-1)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i+1, j-1) + 2\n",
    "                if i < len(word1) <= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans, res)\n",
    "                return res\n",
    "            return max(dfs(i+1, j), dfs(i, j-1))\n",
    "        dfs(0, len(s)-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1+word2#求最长回文序列\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            nonlocal s,ans\n",
    "            if i>j:#i>=len(word1) or j<len(word1)，看看非递归的i，j的遍历顺序就知道了\n",
    "                return 0\n",
    "            if i == j: #f[i][i] = 1\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                #只有递归i < len(word1) <= j，才满足要求\n",
    "                res = dfs(i+1,j-1)+2\n",
    "                if i < len(word1) <= j:\n",
    "                    ans = max(ans,res)  \n",
    "                return res \n",
    "            return max(dfs(i+1,j),dfs(i,j-1))\n",
    "        dfs(0,n-1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        word = word1 + word2\n",
    "        n = len(word)\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j: return 0\n",
    "            if i == j: return 1\n",
    "            if word[i] == word[j]:\n",
    "                res = dfs(i+1, j-1) + 2\n",
    "                if i < len(word1) <= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans, res)\n",
    "                return res\n",
    "            return max(dfs(i+1, j), dfs(i, j-1))\n",
    "        dfs(0, n-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        m = len(word1)\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def f(i,j):\n",
    "            if i>j:\n",
    "                return 0\n",
    "            if i==j:\n",
    "                return 1\n",
    "            if s[i]==s[j]:\n",
    "                nonlocal ans\n",
    "                cur = f(i+1,j-1) + 2\n",
    "                if i<m <= j:\n",
    "                    ans = max(ans,cur)\n",
    "                return cur\n",
    "            return  max(f(i+1,j),f(i,j-1))\n",
    "        f(0, len(s)-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "\n",
    "        @functools.cache\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 1 if i == j else 0\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i + 1, j - 1) + 2\n",
    "                if i < len(word1) <= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans, res)\n",
    "                return res\n",
    "            return max(dfs(i + 1, j), dfs(i, j - 1))\n",
    "\n",
    "        dfs(0, n - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1+word2#求最长回文序列\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            nonlocal s,ans\n",
    "            if i>j :\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                #只有递归i < len(word1) <= j，才有结果\n",
    "                res = dfs(i+1,j-1)+2\n",
    "                if i < len(word1) <= j:\n",
    "                    ans = max(ans,res)  \n",
    "                return res \n",
    "            return max(dfs(i+1,j),dfs(i,j-1))\n",
    "        dfs(0,n-1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i > j: return 0\n",
    "            if i == j: return 1\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i + 1, j - 1) + 2\n",
    "                if i < len(word1) <= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans, res)\n",
    "                return res\n",
    "            return max(dfs(i + 1, j), dfs(i, j - 1))\n",
    "        dfs(0, len(s) - 1)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i > j: return 0\n",
    "            if i == j: return 1\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i + 1, j - 1) + 2\n",
    "                if i < len(word1) <= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans, res)\n",
    "                return res\n",
    "            return max(dfs(i + 1, j), dfs(i, j - 1))\n",
    "        dfs(0, len(s) - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "import sys\n",
    "import random\n",
    "# sys.setrecursionlimit(100000)\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        n1,n2 = len(word1),len(word2)\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def f(l,r):\n",
    "            nonlocal ans\n",
    "            if l > r:\n",
    "                return 0\n",
    "            if l == r:\n",
    "                return 1\n",
    "            res = 0\n",
    "            if s[l] == s[r]:\n",
    "                res = f(l+1,r-1) + 2\n",
    "                if l < n1 and r >= n1:\n",
    "                    ans = max(ans, res)\n",
    "            else:\n",
    "                res = max(f(l+1,r),f(l,r-1))\n",
    "            return res\n",
    "        f(0,n1+n2-1)\n",
    "        return ans \n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(word1)\n",
    "        m = len(word2)\n",
    "        s = word1 + word2\n",
    "        @cache\n",
    "        def f(i,j):\n",
    "            if i>j:\n",
    "                return 0\n",
    "            if i==j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:    \n",
    "                cur = f(i+1,j-1) + 2\n",
    "                if i< n and n <= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans, cur)\n",
    "                return cur\n",
    "            return max(f(i+1,j), f(i,j-1))\n",
    "        f(0,n+m -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        m = len(word1)\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dp(i=0,j=n-1):\n",
    "            nonlocal ans\n",
    "            if i>j: return 0\n",
    "            if i==j: return 1\n",
    "            if s[i] == s[j]:\n",
    "                r = dp(i+1,j-1)+2\n",
    "                if i<m<=j:\n",
    "                    ans = max(ans,r)\n",
    "                return r\n",
    "            return max(dp(i+1,j),dp(i,j-1))\n",
    "        dp()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n = len(s)\n",
    "        n1 = len(word1)\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j :\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i+1, j-1) + 2\n",
    "                if i < n1 <= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(res, ans)\n",
    "                return res\n",
    "            else:\n",
    "                return max(dfs(i+1, j), dfs(i, j-1))\n",
    "        dfs(0, n-1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        m = len(word1)\n",
    "        n = len(word2)\n",
    "        if m == 0 or n == 0:\n",
    "            return 0\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i+1,j-1) + 2\n",
    "                if i < m <= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans,res)\n",
    "                return res\n",
    "            else:\n",
    "                return max(dfs(i+1,j), dfs(i,j-1))\n",
    "        dfs(0,m+n-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s=word1+word2\n",
    "        n=len(s)\n",
    "        #f=[[0]*(n) for _ in range(n)]\n",
    "        ans=0\n",
    "        #for i in range(n-1,-1,-1):\n",
    "        #    f[i][i]=1\n",
    "        #    for j in range(i+1,n):\n",
    "        #        if s[i]==s[j]:\n",
    "        #            f[i][j]=f[i+1][j-1]+2\n",
    "        #            if i<len(word1)<=j:\n",
    "        #                ans=max(ans,f[i][j])\n",
    "        #        else:\n",
    "        #            f[i][j]=max(f[i+1][j],f[i][j-1])\n",
    "        #return ans\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i>j: return 0\n",
    "            if i==j: return 1\n",
    "            if s[i]==s[j]:\n",
    "                res = dfs(i+1,j-1)+2\n",
    "                if i<len(word1)<=j:\n",
    "                    nonlocal ans\n",
    "                    ans=max(ans,res)\n",
    "                return res\n",
    "            return max(dfs(i+1,j),dfs(i,j-1))\n",
    "        dfs(0,n-1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1+word2#求最长回文序列\n",
    "        l1 = len(word1)\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i,j):\n",
    "            nonlocal ans\n",
    "            if i>j:\n",
    "                return 0    \n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                t = dfs(i+1, j-1)+2\n",
    "                if i<l1 and j>= l1:\n",
    "                    ans = max(ans,t)\n",
    "                    # print(ans)\n",
    "                return t\n",
    "            return max(dfs(i+1,j),dfs(i, j-1))\n",
    "        dfs(0, n-1)\n",
    "        # print(ans)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # ans = 0\n",
    "        # dp = [[0]*n for _ in range(n)]\n",
    "        # for i in range(n-1,-1,-1):\n",
    "        #     dp[i][i] = 1 #i == j的时候，结果为1\n",
    "        #     for j in range(i+1,n):\n",
    "        #         if s[i] == s[j]:\n",
    "        #             #只有递归i < len(word1) <= j，才满足要求\n",
    "        #             dp[i][j] = dp[i+1][j-1]+2\n",
    "        #             if i < len(word1) <= j:\n",
    "        #                 ans = max(ans,dp[i][j])  \n",
    "        #         else :\n",
    "        #             dp[i][j] = max(dp[i+1][j],dp[i][j-1])\n",
    "        # return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        self.ans, n = 0, len(s)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j: return 0\n",
    "            if i == j: return 1\n",
    "            res = 0\n",
    "            if s[i] == s[j]:\n",
    "                res = max(res, dfs(i+1, j-1) + 2)\n",
    "                if i < len(word1) <= j:\n",
    "                    self.ans = max(self.ans, res)\n",
    "            else:\n",
    "                res = max(res, dfs(i+1, j), dfs(i, j-1))\n",
    "            \n",
    "            return res \n",
    "        \n",
    "        dfs(0, n-1)\n",
    "        return self.ans \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i >j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i + 1,j - 1) + 2\n",
    "                if i < len(word1) <= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans,res)\n",
    "                return res\n",
    "            return max(dfs(i + 1,j),dfs(i,j - 1))\n",
    "        \n",
    "        dfs(0,len(s) - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        n = len(word1)\n",
    "        m = len(word2)\n",
    "        s = word1 + word2\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def f(i,j):\n",
    "            if i>j:\n",
    "                return 0\n",
    "            if i==j:    \n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                cur = f(i+1,j-1) + 2\n",
    "                if i<n<= j:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans,cur)\n",
    "                return cur\n",
    "            return max(f(i+1,j)    , f(i,j-1))\n",
    "        f(0,m+n-1)\n",
    "        return ans\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n, m = len(word1), len(word2)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            elif i == j:\n",
    "                return 1\n",
    "            elif s[i] == s[j]:\n",
    "                return dfs(i + 1, j - 1) + 2\n",
    "            return max(dfs(i, j - 1), dfs(i + 1, j))\n",
    "            \n",
    "        res = 0\n",
    "        for h in range(m - 1, -1, -1):\n",
    "            if word2[h] in word1:\n",
    "                res = max(res, dfs(word1.find(word2[h]), n + h))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s = word1 + word2\n",
    "        n, m = len(word1), len(word2)\n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            elif i == j:\n",
    "                return 1\n",
    "            elif s[i] == s[j]:\n",
    "                return dp(i + 1, j - 1) + 2\n",
    "            return max(dp(i, j - 1), dp(i + 1, j))\n",
    "            \n",
    "        res = 0\n",
    "        for h in range(m - 1, -1, -1):\n",
    "            if word2[h] in word1:\n",
    "                res = max(res, dp(word1.find(word2[h]), n + h))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "最长回文串\n",
    "f[i][j]=f[i+1][j],f[i][j-1],f[i+1][j-1]+2\n",
    "'''\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        s1=set(word1)\n",
    "        s2=set(word2)\n",
    "        if not s1&s2:\n",
    "            return 0\n",
    "        f=[[0]*len(word1) for _ in range(len(word1)+1)]\n",
    "        for i in range(len(word1)-1,-1,-1):\n",
    "            for j in range(i+1,len(word1)):\n",
    "                f[i][i]=1\n",
    "                if word1[i]==word1[j]:\n",
    "                    f[i][j]=f[i+1][j-1]+2\n",
    "                else:\n",
    "                    f[i][j]=max(f[i+1][j],f[i][j-1])\n",
    "        g=[[0]*len(word2) for _ in range(len(word2)+1)]\n",
    "        for i in range(len(word2)-1,-1,-1):\n",
    "            for j in range(i+1,len(word2)):\n",
    "                g[i][i]=1\n",
    "                if word2[i]==word2[j]:\n",
    "                    g[i][j]=g[i+1][j-1]+2\n",
    "                else:\n",
    "                    g[i][j]=max(g[i+1][j],g[i][j-1])\n",
    "        \n",
    "\n",
    "        @cache\n",
    "        def dfs(i:int,j:int,choose:bool)->int:\n",
    "            if i>=len(word1):\n",
    "                if not choose:return -inf\n",
    "                return g[0][j] if j>=0 else 0\n",
    "            if j<0:\n",
    "                if not choose:return -inf\n",
    "                return f[i][len(word1)-1] if i<len(word1) else 0\n",
    "            ans=-inf\n",
    "            if word1[i]==word2[j]:\n",
    "                ans=dfs(i+1,j-1,True)+2\n",
    "            ans=max(ans,dfs(i,j-1,choose),dfs(i+1,j,choose))\n",
    "            return ans\n",
    "        ans=dfs(0,len(word2)-1,False)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        l1 = len(word1)\n",
    "        l2 = len(word2)\n",
    "        s = word1+word2\n",
    "        @cache\n",
    "        def dfs(i,j,flag):#添加状态\n",
    "            # if i == l1 and j == l1 and flag:\n",
    "            #     return 1\n",
    "            # elif i==l1-1 and j== l1-1 and flag:\n",
    "            #     return 1\n",
    "            if i==j and flag:\n",
    "                return 1\n",
    "            elif i>j:\n",
    "                return 0\n",
    "            elif j<l1 and not flag:\n",
    "                return 0\n",
    "            elif i>l1-1 and not flag:\n",
    "                return 0\n",
    "                \n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i+1,j-1,True) + 2\n",
    "            else:\n",
    "                return max(dfs(i+1,j,flag),dfs(i,j-1,flag)) #\n",
    "        return dfs(0,l1+l2-1,False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, word1: str, word2: str) -> int:\n",
    "        n, m = len(word1), len(word2)\n",
    "        s = word1+word2\n",
    "        @cache\n",
    "        def helper(i, j, pick): # pick表示之前是否选过\n",
    "            if i>j:\n",
    "                return 0\n",
    "            if i>=n and not pick: # 超过边界还没选，直接返回0，不能只选一边，若是已经选过了，那么另一边多出来的部分只要能组成回文串，就可以继续选\n",
    "                return 0\n",
    "            if j<n and not pick:\n",
    "                return 0\n",
    "            if i==j:\n",
    "                return 1\n",
    "            if s[i]==s[j]:\n",
    "                return helper(i+1, j-1, True)+2\n",
    "            else:\n",
    "                return max(helper(i+1, j, pick), helper(i, j-1, pick))\n",
    "        return helper(0, n+m-1, False)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
